public class NondeterministicFiniteAutomata extends FiniteAutomata
{
	/*
	 * MEMBER VARIABLES
	 */
	
	private String[] _activeStates;
	
	
	
	/*
	 * CONSTRUCTORS
	 */
	
	public NondeterministicFiniteAutomata(String input)
	{
		super(input);
		this._activeStates = new String[1];
	}
	
	
	
	/*
	 * CONCRETE METHODS
	 */
	
	// Remember to verify this is a VALID and COMPLETE NFA before calling! 
	// NO checks are performed here, they MUST be done beforehand
	// Call isValid() first!  
	@Override
	public boolean simulate(String[] word) // Note:  word[0] will be null, ignore
	{
		this._activeStates = new String[1];
		this._activeStates[0] = this._states[0].getName();
		this._activeStates = this.doEpsilonTransitions(this._activeStates);
		// Will hold (temporarily) all the states that become active after
		// reading the first letter.  
		String[] newActiveStates = new String[this._stateCount];
		int activeStates = 0;
		for (int i = 1; i < word.length; i++)
		{ // For each letter in the word...  
			for (String activeState : this._activeStates)
			{ // For each currently active state...  
				// Get the next states for this state, including
				// states from epsilon transitions
				String[] nextStates = this.getStateFromName(activeState).NFAtrans(word[i], this._stateCount);
				nextStates = this.doEpsilonTransitions(nextStates);
				for (String next : nextStates)
				{ // Then add only the states not already in newActiveStates
					boolean inThere = false;
					for (int k = 0; k < activeStates; k++)
					{
						if (newActiveStates[k].equals(next))
						{
							inThere = true;
						}
					}
					if (!inThere)
					{
						newActiveStates[activeStates] = next;
						activeStates++;
					}
				}
			}
			// Clear _activeStates and add the new active states
			this._activeStates = new String[activeStates];
			for (int j = 0; j < activeStates; j++)
			{
				this._activeStates[j] = newActiveStates[j];
			}
			activeStates = 0;
			newActiveStates = new String[this._stateCount];
		}
		// Do the final epsilon transitions
		this._activeStates = this.doEpsilonTransitions(this._activeStates);
		for (String state : this._activeStates)
		{ // Check for accepting states
			if (this.getStateFromName(state).getAccepting())
			{
				return true;
			}
		}
		// :-(  
		return false;
	}
	
	// Runs all the states in "states" through epsilon transitions
	// over and over again until new states stop pouring in.  
	public String[] doEpsilonTransitions(String[] states)
	{
		// newStates will store all states present in "states", as well
		// as all states that can be gotten to by epsilon transitions from
		// a state in "states".  
		String[] newStates = new String[this._stateCount];
		for (int i = 0; i < states.length; i++)
		{
			newStates[i] = states[i];
		}
		int newCount = states.length;
		for (String string : states)
		{ // For each state in states...  
			// Do an epsilon transition for that state
			String[] newNewStates = this.getStateFromName(string).NFAtrans("", this._stateCount);
			boolean isIn = false;
			for (String newNewString : newNewStates)
			{ // For each of those epsilon transitions...  
				for (int k = 0; k < newCount; k++)
				{ // Check if that new state is already in newStates
					if (newStates[k].equals(newNewString))
					{
						isIn = true;
					}
				}
				if (!isIn)
				{ // If not, put it in
					newStates[newCount] = newNewString;
					newCount++;
				}
			}
		}
		if (newCount == states.length)
		{ // No new states were added, so we're done
			return states;
		}
		else
		{ // We added new states via epsilon transitions
			// So see if those new states have any epsilon transitions
			// The String[] passed to this method must have the correct size
			String[] finalStrings = new String[newCount];
			for (int j = 0; j < newCount; j++)
			{
				finalStrings[j] = newStates[j];
			}
			return doEpsilonTransitions(finalStrings);
		}
	}
	
	@Override
	public boolean containsLetter(String letter)
	{
		if (letter.equals("")) { return true; }
		for (String l : this._alphabet)
		{
			if (l.equals(letter))
			{
				return true;
			}
		}
		return false;
	}

	// Checks if the NFA is valid and complete.  
	// Note that this won't always be the case.  
	// Partially completed NFAs can be saved.  
	// Very similar, but notably not identical to, 
	// this function for DFAs.  
	@Override
	public String isValid()
	{
		// First make sure there's a starting state.  
		if (this._states[0] == null)
		{
			return "No starting state.";
		}
		// Note that it's okay to not have any accepting states.  Just dumb. 
		String[] names = new String[this._stateCount - 1];
		int m = 0;
		for (int i = 1; i <= this._stateCount; i++)
		{
			// Then make sure no two states share the same name.  
			for (int j = 0; j < m; j++)
			{
				if (this._states[i].getName().equals(names[j]))
				{
					return "There are two states with the name " + this._states[i].getName() + ".";
				}
			}
			names[m] = this._states[i].getName();
			// Finally, make sure no states have transitions for letters
			// that aren't in the alphabet.  
			String[] transitions = this._states[i].getTransitions();
			int transitionCount = this._states[i].getTransitionCount();
			for (int j = 0; j < transitionCount; j++)
			{
				if (!this.containsLetter(transitions[2 * j]))
				{
					return this._states[i].getName() + " has a transition for the letter " + transitions[2 * j] + ", which is not in the alphabet.";
				}
			}
		}
		// Note that the last three checks would each need their own
		// identical loop from i = 1 to this._stateCount if they didn't
		// share the one they're in.  
		return "VALID";
	}
}